home *** CD-ROM | disk | FTP | other *** search
/ The Fatted Calf / The Fatted Calf.iso / Applications / Games / NeXTGo / Source / smartgotree.c < prev    next >
C/C++ Source or Header  |  1993-02-08  |  6KB  |  401 lines
  1. #include "comment.header"
  2.  
  3. #include "smartgo.h"
  4.  
  5. /*  Define the following variable for debugging information.  */
  6. /*  #define _DEBUG_ON_  */
  7.  
  8. #ifdef _DEBUG_ON_
  9. #include <stdio.h>
  10.  
  11. void display_tree(node* root_node)
  12. {
  13.   node *tnode;
  14.  
  15.   tnode = root_node;
  16.  
  17.   while (tnode != NULL)
  18.     {
  19.       if (tnode->properties != NULL)
  20.     printf(";");
  21.       if (tnode->variants != NULL)
  22.     {
  23.       printf("(");
  24.       display_tree(tnode->variants);
  25.       printf(")");
  26.     }
  27.       if (tnode->next == NULL)
  28.     {
  29.       while (tnode->prev != NULL)
  30.         tnode = tnode->prev;
  31.       tnode = tnode->next_var;
  32.       if (tnode != NULL)
  33.         printf(")(");
  34.     }
  35.       else
  36.     {
  37.       tnode = tnode->next;
  38.     }
  39.     }
  40. }
  41. #endif
  42.  
  43. node* forwardOneNode(node* currentNode)
  44. {
  45.   node *tnode;
  46.  
  47.   if (currentNode->variants != NULL)
  48.     {
  49.       return currentNode->variants;
  50.     }
  51.   else if (currentNode->next != NULL)
  52.     {
  53.       return currentNode->next;
  54.     }
  55.   else
  56.     {
  57.       tnode = currentNode;
  58.       while (tnode->prev != NULL)
  59.     tnode = tnode->prev;
  60.       if (tnode->next_var != NULL)
  61.     {
  62.       return tnode->next_var;
  63.     }
  64.       else
  65.     {
  66.       return forwardOneNode0(currentNode->parent);
  67.     }
  68.     }
  69. }
  70.  
  71. node* forwardOneNode0(node* currentNode)
  72. {
  73.   node *tnode;
  74.  
  75.   if (currentNode->next != NULL)
  76.     {
  77.       return currentNode->next;
  78.     }
  79.   else
  80.     {
  81.       tnode = currentNode;
  82.       while (tnode->prev != NULL)
  83.     tnode = tnode->prev;
  84.       if (tnode->next_var != NULL)
  85.     {
  86.       return tnode->next_var;
  87.     }
  88.       else
  89.     {
  90.       if (currentNode->parent != NULL)
  91.         {
  92.           return forwardOneNode0(currentNode->parent);
  93.         }
  94.       else
  95.         {
  96.           return tnode;
  97.         }
  98.     }
  99.     }
  100. }
  101.  
  102. node* backOneNode(node* currentNode)
  103. {
  104.   if (currentNode->prev != NULL)
  105.     {
  106.       if (currentNode->prev->variants != NULL)
  107.     {
  108.       return findLast(currentNode->prev->variants);
  109.     }
  110.       else
  111.     {
  112.       return currentNode->prev;
  113.     }
  114.     }
  115.   else
  116.     {
  117.       if (currentNode->prev_var != NULL)
  118.     {
  119.       return findLast0(currentNode->prev_var);
  120.     }
  121.       else
  122.     {
  123.       if (currentNode->parent != NULL)
  124.         {
  125.           return currentNode->parent;
  126.         }
  127.       else
  128.         {
  129.           return findLast(currentNode);
  130.         }
  131.     }
  132.     }
  133. }
  134.  
  135. node* findLast(node* currentNode)
  136. {
  137.   node *tnode;
  138.  
  139.   tnode = currentNode;
  140.  
  141.   while (tnode->next_var != NULL)
  142.     tnode = tnode->next_var;
  143.  
  144.   while (tnode->next != NULL)
  145.     tnode = tnode->next;
  146.  
  147.   if (tnode->variants != NULL)
  148.     {
  149.       return findLast(tnode->variants);
  150.     }
  151.   else
  152.     {
  153.       return tnode;
  154.     }
  155. }
  156.  
  157. node* findLast0(node* currentNode)
  158. {
  159.   node *tnode;
  160.  
  161.   tnode = currentNode;
  162.  
  163.   while (tnode->next != NULL)
  164.     tnode = tnode->next;
  165.  
  166.   if (tnode->variants != NULL)
  167.     {
  168.       return findLast(tnode->variants);
  169.     }
  170.   else
  171.     {
  172.       return tnode;
  173.     }
  174. }
  175.  
  176. node* forwardOneVariant(node* currentNode)
  177. {
  178.   node *tnode;
  179.  
  180.   tnode = currentNode;
  181.  
  182.   while (tnode->prev != NULL)
  183.     tnode = tnode->prev;
  184.  
  185.   if (tnode->next_var != NULL)
  186.     {
  187.       return tnode->next_var;
  188.     }
  189.   else
  190.     {
  191.       return tnode->parent->variants;
  192.     }
  193. }
  194.  
  195. node* backOneVariant(node* currentNode)
  196. {
  197.   node *tnode;
  198.  
  199.   tnode = currentNode;
  200.  
  201.   while (tnode->prev != NULL)
  202.     tnode = tnode->prev;
  203.  
  204.   if (tnode->prev_var != NULL)
  205.     {
  206.       return tnode->prev_var;
  207.     }
  208.   else
  209.     {
  210.       while (tnode->next_var != NULL)
  211.     tnode = tnode->next_var;
  212.  
  213.       return tnode;
  214.     }
  215. }
  216.  
  217. void clearNodeFlags(node* currentNode)
  218. {
  219.   node *r, *v;
  220.  
  221.   r = currentNode;
  222.   while (r != NULL)
  223.     {
  224.       r->flag = 0;
  225.       v = r->variants;
  226.       while (v != NULL)
  227.     {
  228.       clearNodeFlags(v);
  229.       v = v->next_var;
  230.     }
  231.       r = r->next;
  232.     }
  233. }
  234.  
  235. int foundNode;
  236.  
  237. int evaluateSteps(node* currentNode, node* targetNode, unsigned char b[19][19])
  238. {
  239.   node *tnode, *vnodes;
  240.   int i, j;
  241.   extern int MAXX, MAXY;
  242.   unsigned char b0[19][19];
  243.  
  244.   for (i = 0; i < 19; i++)
  245.     for (j = 0; j < 19; j++)
  246.       b0[i][j] = b[i][j];
  247.  
  248.   tnode = currentNode;
  249.   while (tnode != targetNode)
  250.     {
  251.       if (tnode->properties != NULL)
  252.     {
  253.       evaluateNode(tnode->properties, b0);
  254.       tnode->flag = 1;
  255.     }
  256.  
  257.       vnodes = tnode->variants;
  258.       while (vnodes != NULL)
  259.     {
  260.       evaluateSteps(vnodes, targetNode, b0);
  261.       if (foundNode)
  262.         {
  263.           for (i = 0; i < MAXX; i++)
  264.         for (j = 0; j < MAXY; j++)
  265.           b[i][j] = b0[i][j];
  266.  
  267.           return 0;
  268.         }
  269.       vnodes = vnodes->next_var;
  270.     }
  271.  
  272.       if (tnode->next == NULL)
  273.     return 0;
  274.  
  275.       tnode = tnode->next;
  276.     }
  277.  
  278.   if (tnode == targetNode)
  279.     {
  280.       foundNode = 1;
  281.     }
  282.  
  283.   if ((tnode == targetNode) && (!tnode->flag) && (tnode->properties != NULL))
  284.     {
  285.       evaluateNode(tnode->properties, b0);
  286.       tnode->flag = 1;
  287.  
  288.       for (i = 0; i < MAXX; i++)
  289.     for (j = 0; j < MAXY; j++)
  290.       b[i][j] = b0[i][j];
  291.     }
  292.  
  293.   return 0;
  294. }
  295.  
  296. void buildToNode(node* targetNode)
  297. {
  298.   int i, j;
  299.   extern int blackCaptured, whiteCaptured;
  300.   extern unsigned char p[19][19];
  301.   extern node* rootNode;
  302.  
  303.   for (i = 0; i < 19; i++)
  304.     for (j = 0; j < 19; j++)
  305.       p[i][j] = 0;
  306.   blackCaptured = whiteCaptured = 0;
  307.  
  308.   foundNode = 0;
  309.  
  310.   clearNodeFlags(rootNode);
  311.   evaluateSteps(rootNode, targetNode, p);
  312. }
  313.  
  314. node* stepForward(node* currentNode)
  315. {
  316.   node *tnode;
  317.   extern node *rootNode;
  318.  
  319.   tnode = currentNode;
  320.   do
  321.     {
  322.       tnode = forwardOneNode(tnode);
  323.     }
  324.   while ((tnode->properties == NULL) && (tnode != currentNode));
  325.  
  326.   if (tnode == currentNode)
  327.     {
  328.       tnode = rootNode;
  329.  
  330.       do
  331.     {
  332.       tnode = forwardOneNode(tnode);
  333.     }
  334.       while (tnode->properties == NULL);
  335.     }
  336.  
  337.   buildToNode(tnode);
  338.  
  339.   return tnode;
  340. }
  341.  
  342. node* stepBackward(node* currentNode)
  343. {
  344.   node *tnode;
  345.   extern node *rootNode;
  346.  
  347.   tnode = currentNode;
  348.   do
  349.     {
  350.       tnode = backOneNode(tnode);
  351.     }
  352.   while ((tnode->properties == NULL) && (tnode != currentNode));
  353.  
  354.   if (tnode == currentNode)
  355.     {
  356.       tnode = rootNode;
  357.  
  358.       tnode = findLast(tnode);
  359.     }
  360.  
  361.   buildToNode(tnode);
  362.  
  363.   return tnode;
  364. }
  365.  
  366. node* jumpForward(node* currentNode)
  367. {
  368.   node *tnode;
  369.  
  370.   tnode = currentNode;
  371.  
  372.   tnode = forwardOneVariant(tnode);
  373.  
  374.   while (tnode->properties == NULL)
  375.     {
  376.       tnode = forwardOneNode(tnode);
  377.     }
  378.  
  379.   buildToNode(tnode);
  380.  
  381.   return tnode;
  382. }
  383.  
  384. node* jumpBackward(node* currentNode)
  385. {
  386.   node *tnode;
  387.  
  388.   tnode = currentNode;
  389.   tnode = backOneVariant(tnode);
  390.  
  391.   while (tnode->properties == NULL)
  392.     {
  393.       tnode = forwardOneNode(tnode);
  394.     }
  395.  
  396.   buildToNode(tnode);
  397.  
  398.   return tnode;
  399. }
  400.  
  401.